/**
 * Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
 */
package com.xinpan.exercise;

public class PartitionList {
    public ListNode partition(ListNode head, int x) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head == null)
            return null;
            
        ListNode sh = null;
        ListNode sc = null;
        ListNode lh = null;
        ListNode lc = null;
        while(head != null)
        {
            if(head.val < x)
            {
                if(sh == null)
                {
                    sh = head;
                    sc = sh;
                }
                else
                {
                    sc.next = head;
                    sc = sc.next;
                }
            }
            else
            {
                if(lh == null)
                {
                    lh = head;
                    lc = lh;
                }
                else
                {
                    lc.next = head;
                    lc = lc.next;
                }
            }
            head = head.next;
        }
        if(sh == null)
        {
            lc.next = null;
            return lh;
        }
        
        sc.next = lh;
        if(lc != null)
            lc.next = null;
            
        return sh;
    }
}
